In a motor vehicle having a power transmission powered by an engine through a fluid coupling or a torque converter, it is usual to equip the vehicle with a parking brake mechanism which is capable of anchoring the output shaft of the power transmission when secure parking of the vehicle is required. Usually, the parking brake mechanism comprises a swingable brake pawl having at its one end a tooth, a brake gear having a plurality of external teeth and coaxially mounted on the output shaft of the transmission, and a parking cam for urging the tooth of the brake pawl into engagement with a gap formed between any corresponding two of the teeth of the brake gear in response to shifting of the transmission shift lever into the parking position. However, in the conventional parking brake mechanism of a type mentioned above, it is observed that the tooth of the brake pawl is formed, at a portion facing the outer peripheral surface of the brake gear, with a substantially flat surface. It can, with this kind brake pawl, undesirably occur that just a slight insertion of the tooth into the gap instantly induces complete locking engagement of the tooth with the brake gear to lock the transmission output shaft. This phenomenon will cause a very dangerous situation if by chance miss-shifting of the transmission shift lever into the parking position during high speed running of the vehicle occurs, whereby complete the locking of the output shaft takes place. Doubtless, this is very dangerous, not to mention possible damage to bearings and twisting of torque transmitting shafts throughout the transmission, shattering of teeth on the brake gear and the like.